import java.util.ArrayList;
import java.util.Arrays;


public class Solution {
    public int findKth (int[] a, int n, int K) {
        // write code here
        //有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。
        //给定一个整数数组 a ,同时给定它的大小n和要找的 k ，
        // 请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。

        if(){
            //
        }

        return 0;

    }
    public ArrayList<Integer> GetLeastNumbers_Solution (int[] input, int k) {
        /*给定一个长度为 n 的可能有重复值的数组，
        找出其中不去重的最小的 k 个数。
        例如数组元素是4,5,1,6,2,7,3,8这8个数字，
        则最小的4个数字是1,2,3,4(任意顺序皆可)。

        */
        // write code here
        ArrayList<Integer> arrInteger = new ArrayList<>();
        if(k==0){
            return arrInteger;
        }

        int[] arr = new int[k];
        for (int i = 0; i < k; i++) {
                arr[i] = input[i];
        }
        Arrays.sort(arr);

        for (int i = k; i < input.length; i++) {
            if (input[i] < arr[k-1]) {
                arr[k-1] = input[i];
                Arrays.sort(arr);
            }
        }
        for(int i = 0; i < k; i++) {
            arrInteger.add(arr[i]);
        }
        return arrInteger;
    }
}
